% !Mode:: "TeX:UTF-8"

\chapter{相关理论基础}
\section{概率模型}
在机器学习最首要的任务，是根据已观察到的证据，来对感兴趣的未知变量进行估计和推测\citeup{zhouzhihua}。前者就是所谓的训练样本，而后者通常为类别标记。概率模型（probabilistic model）提供了一种描述框架，将整个机器学习要完成的任务抽象为计算随机变量的概率分布。

概率模型通常分为产生式模型和生成式模型，假设我们关心的变量集合为\(Y\)，可观测的变量集合为\(O\)，其他变量的集合为\(R\)。生成式模型考虑联合分布\(P(Y, R, O)\)，而判别式模型考虑的则是条件分布\(P(Y, R | O)\)。在给定观测变量值的条件下，概率模型所做的推断工作，即是从考虑的分布中的得到条件概率分布\(P(Y | O)\)。

当我们仅考虑各种变量集合为离散状态的时候，由于为联合分布，考虑所有情况下求和消除变量\(R\)即可解出条件概率分布\(P(Y | O)\)，但由于算法复杂度极高并不现实。同样，由于特征向量之间往往相关，为了能够针对不同的情况研究高效的学习算法，人们发明了概率图模型（probabilistic graphical model）。

\section{概率图模型}
为了能够简洁紧凑地研究变量之间的概率关系，使用了图的形式作为表示工具。一般用一个结点表示一组随机变量，结点之间的边表示变量之间的概率相关关系。概率图模型通常分为两类：使用有向无环图表示变量之间依赖关系，成为有向图模型；使用无向图表示变量之间的相关关系，称为无向图模型。这里举三个模型为例进行详细描述和比较。
\subsection{隐马尔科夫模型}
隐马尔科夫模型（Hidden Markov Model，简称HMM），是非常著名的生成式有向图模型之一。主要用于对时序数据的建模，在自然语言处理、语音识别等领域有非常广泛的应用。

\pic [htbp]{隐马尔科夫模型的图结构}{width=0.6\textwidth}{HMM}

如图\ref{HMM}，位于上方的结点表示状态变量\(\{y_1,y_2,...,y_n\}\)，其中\(y_i \epsilon Y\)表示第\(i\)时刻的系统状态，通常状态变量不可被观测。下方的结点则表示观测变量\(\{x_1,x_2,...,x_n\}\)，其中\(x_i \epsilon X\)表示同一\(i\)时刻的观测值。图中的箭头表示变量间的依赖关系，可见，某一时刻观测变量值\(x_t\)仅依赖于状态变量\(y_t\)，与其他的状态变量取值无关系。同时某时刻状态变量\(y_t\)的取值，也仅仅相关于前一时刻的状态变量取值，与其他任何状态变量取值无关。人们在此模型上定义了马尔科夫性质，此性质描述为：某一系统在下一状态的概率仅与当前状态有关，而与之前的状态无关。基于这种性质，所有变量的联合分布为：\begin{equation}P(x_1,y_1,...,x_n,y_n)=P(y_1)P(x_1|y_1)\prod_{i=2}^{n}P(y_i|y_{i-1})P(x_i | y_i) \end{equation} 

假设系统在多个状态\(\{s_1,s_2,...,s_n\}\)之间转换，那么状态变量的\(y_i\)的取值范围\(Y\)即是有N个可能取值的离散空间。这个空间我们称为状态空间。假如观测变量取值范围\(X\)为\(\{o_1,o_2,...,o_n\}\)，此取值范围被称作观测空间。

初始时刻时，系统应该处于某一个状态，这个状态是根据初始状态概率决定的。由于状态只有N个可能取值，所以可以记为\(\boldsymbol{\pi} = (\pi_1,\pi_2,...,\pi_N)\)。其中\begin{equation}\pi_i = P(y_1 = s_i), 1 \le i \le N \end{equation}表示模型的初始状态为\(s_i\)的概率。

下一时刻，模型将转化为下一个状态，将会转化为哪一个状态，则需要参考一个N行N列的矩阵。通常记为\(\boldsymbol{A} = [a_{ij}]_{N \times N}\)，其中\begin{equation}a_{ij} = P(y_{t+1} = s_j | y_t = s_i), 1 \le i, j \le N\end{equation}表示任意时刻\(t\)，若状态为\(s_i\)，则在下一时刻为\(s_j\)的概率。

每一时刻，我们希望得到对应当前状态的观测值的概率，由于观测值可能有M种取值，这里记为矩阵\(\boldsymbol{B} = [b_{ij}]_{N \times M}\)，其中\begin{equation}b_{ij} = P(x_t = o_j | y_t = s_i), 1 \le i \le N, 1\le j \le M\end{equation}表示任意时刻\(t\)若状态为\(s_i\)，观测值为\(o_j\)的概率。

至此，我们有了状态空间\(Y\)，观测空间\(X\)和三个概率矩阵，便能构建一个隐马尔科夫模型。

根据上文，我们可以将一个马尔科夫模型用其参数表示，即\(\lambda = [\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi}]\)\citeup{zhouzhihua}。结合应用来讨论我们利用隐马尔科夫解决的三类问题，以便于与其他模型构成类比。

（1）模型与观测序列之间的匹配程度：即给定模型\(\lambda = [\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi}]\)，计算其产生\(\boldsymbol{x}\)的概率\(P(\boldsymbol{x} | \lambda)\)。比如一个预测任务，在已知以往的观测序列，推断当前最有可能的观测值。

（2）根据观测序列推断状态变化：即给定\(\lambda = [\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi}]\)和观测序列，找到与其依次对应的状态序列。比如说在语音识别的任务中，观测序列为语音信号序列，而状态为字符序列，目标就是根据信号序列推断最有可能的字符序列。

（3）根据观测序列，如何调整\(\lambda = [\boldsymbol{A},\boldsymbol{B},\boldsymbol{\pi}]\)参数，以求该序列出现的概率最大？这便是一个使用一定量训练数据训练模型参数的过程。

基于变量联合分布的条件独立性，这三个问题都能高效求解\citeup{zhouzhihua}。

\subsection{马尔科夫随机场}

\pic [htbp]{一个马尔科夫随机场的图结构}{width=0.6\textwidth}{MRF}
与隐马尔科夫相同的是，马尔科夫随机场同样为生成式模型，即对联合分布进行建模。但却为一种无向图模型（又称为马尔科夫网）。在一个表示马尔科夫随机场的无向图中，每一个结点都表示一个或一组变量。结点之间的边表示两个变量之间的依赖。为了能够准确地描述马尔科夫随机场的联合概率分布，在此阐明一些概念。

\subsubsection{团与最大团}
对于给定无向图\(G = (V,E)\)，一个两两之间有变的结点集合便是此图的团（clique）。若一个团中加入任何一个结点都不再形成团，那么这个团就称作“极大团”（maximal clique）。也就是说，极大团不能被任何团包含，即不是其他任何一个团的真子集。顶点最多的极大团，称为图\(G\)的“最大团”（maximum clique）。
\subsubsection{势函数}
势函数是一个表示其对应团状态的非负实值函数，即一个定义在团上的测度（Measure）。测度是一个函数，把给定集合的某个子集指定一个数，这个数可以代表大小、体积、概率等。在马尔科夫随机场中，一个势函数可以看做无向图中某个团映射到代表概率的某个数。

\subsubsection{马尔科夫随机场的概率分布函数}
有了团和势函数的定义，多个变量之间的联合概率分布便可以基于团分解为多个势函数的乘积，每个势函数仅与一个团相关。具体来说，对于n个变量\(\boldsymbol{x} = \{x_1, x_2, ... ,x_n\}\)，所有团构成的集合为\(C\)，与团\(Q\in C\)对应的变量集合为\(\boldsymbol{x}_Q \)，则联合概率\(P(\boldsymbol{x})\)定义为
\begin{equation}P(\boldsymbol{x}) = \frac{1}{Z} \prod_{Q\in C} \Psi_Q (\boldsymbol{x}_Q)\end{equation}
其中\(\Psi_Q\)为与团\(Q\)对应的势函数，用于对团\(Q\)中的变量模型进行建模，因为概率应该在0和1之间，所以需要一个规范化因子\(Z\)，定义为
\begin{equation}Z= \sum_{\boldsymbol{x}} \prod_{Q \in C} \Psi (\boldsymbol{x}_Q)\end{equation}
用于确保\(P(\boldsymbol{x})\)是被正确定义的概率。

\subsection{条件随机场模型}

\pic [htbp]{链式条件随机场的图结构}{width=0.6\textwidth}{CRF}
与隐马尔科夫模型不同，条件随机场（Conditional Random Field，简称CRF）则是一种判别式无向图模型。

在本章第一节介绍过，生成式模型对条件分布进行建模。在已经获得一个观测序列的即多个变量的观测值的情况下，CRF在此观测序列的基础上建立条件概率模型：若令\(\boldsymbol{x}=\{x_1, x_2, ..., x_n\}\)为观测序列，\(\boldsymbol{y} = \{y_1, y_2, ..., y_n\}\)为与之相对应的标记序列，CRF希望建立一个条件概率模型\(P(\boldsymbol{y} | \boldsymbol{x})\)。CRF在自然语言处理领域应用非常广泛，比如词性标注，观测数据为单词构成的短语，标记为每个短语中单词的词性序列。

假设有一无向图\(G=<V,E>\)，其中每一结点\(v\)对应一个标记变量\(y_v\)，\(n(v)\)表示结点\(v\)的临近结点。若图\(G\)的每一个变量都具有马尔科夫性，即：
\begin{equation}P(y_v | \boldsymbol{x}, \boldsymbol{y}_{ V \backslash \{v\} })=P(y_v | \boldsymbol{x}, \boldsymbol{y}_{n(v)})\end{equation}，
\((\boldsymbol{y},\boldsymbol{x})\)构成一个条件随机场。

由于的工作为命名实体识别，实际上是对标记序列建模，其使用的如图\ref{CRF}所示的链式结构。我们主要讨论这种条件随机场。

条件随机场也可以使用势函数和团来定义条件概率\(P(\boldsymbol{y} | \boldsymbol{x})\)。给定观测序列\(\boldsymbol{x}\)，选择指数势函数并引入特征函数，就可以这样定义条件概率
\begin{equation}P(\boldsymbol{y} | \boldsymbol{x}) = \frac{1}{Z} exp(\sum_j \sum_{i=1}^{n-1}\lambda_j t_j (y_{i+1}, y_i, \boldsymbol{x}, i) + \sum_k \sum_{i=1}^n \mu_k s_k (y_i, \boldsymbol{x}, i))\end{equation}
其中，\(t_j\)是定义在观测序列两个相邻标记位置上的转移特征函数，可以看做是定义在图中两个表示相邻标记变量的结点之间的边上的转移特征函数（transition feature function），用来刻画相邻标记变量之间的相关关系和观测序列对其影响，\(s_k\)是定义在观测序列的标记位置上的状态特征函数（state feature function），用于刻画观测序列对标记变量的影响，\(\lambda_j\)和\(\mu_k\)为参数。同时也拥有规范化因子\(Z\)用于保证概率正确定义。

所谓特征函数是一组实值函数，观察公式可以看出，每个函数与一个特征权重相对应。在模型训练前，特征函数实际上是确定的，训练过程就是得到特征函数权重的过程。下面结合一个标注任务例子来解释转移特征函数和状态特征函数。

假如有一个词性标注任务，如表\ref{exampleofmarkwords}
\threelinetable[htbp]{exampleofmarkwords}{0.3\textwidth}{lcr}{一个词性标注任务示例}
{观测序列&标记序列\\}
{
The & [D] \\
boy & [N] \\
knocked & [V] \\
at & [P]\\
the & [D]\\
watermelon & [N]\\
}
{
}
则某个转移特征函数如下
\[t_j(y_{i+1}, y_i, \boldsymbol{x}, i)=\begin{cases}
1 &\text{if \(y_{i+1} = [P], y_i = [V]\)  and  \(x_i = "knocked"\)},\\
0 & \text{otherwise,}
\end{cases}\]
表示第\(i\)个观测值\(x_i\)为单词knocked时，其标记很可能是[V]，并且后一个标记很可能是[P]。而状态特征函数如下
\[s_k(y_i, \boldsymbol{x}, i)=\begin{cases}
1 &\text{if \(y_i = [V]\)  and  \(x_i = "knocked"\)},\\
0 & \text{otherwise,}
\end{cases}\]
表示第\(i\)个观测值\(x_i\)为单词knocked时，其标记很可能是[V]。

由此可见，在使用条件随机场的时候，首先要确定某种特征函数，并确定此特征函数集合。

CRF是给定观察序列的情况下，计算整个观察序列对应的标记序列的联合概率分布，而不是给定当前状态标记下一个状态。标记序列的条件分布属性，让CRF可以很好地拟合标记序列的条件概率依赖于观察序列中非独立的特征数据。CRF模型近年来广泛应用于序列标注问题中\citeup{zhou2006cengdiecrf,ju2011crfguizedili,he2015crfguize}，并且在多个研究领域都取得了良好的效果。因为条件随机场模型综合了隐马尔科夫模型和最大熵模型的有点，并克服了HMM模型那样严格的独立性假设，并解决了标记偏置缺点。

\section{本章小结}
本章首先宏观地介绍了概率模型是通过概率值排序或者通过全局及局部方式对概率空间进行最优搜索来判别目标的数学模型。并由此引出了研究概率模型的重要工具，概率图模型。并从隐马尔科夫模型开始，介绍了概率图模型通常解决的问题及解决方法中条件独立性的重要性，再通过引入势函数和团的概念，介绍了马尔科夫随机场和条件随机场，循序渐进地解释了生成式模型与判别式模型、无向图模型与有向图模型之间的区别。最终，通过模型本身的特点及相关研究，确定了CRF模型在解决序列标注问题上具有优势。
